'''
Created on Jun 10, 2012

@author: Timothy A. Mann
'''

def generate_primes(upTo):
    """
    Generates a list of prime numbers up to a specified value.
    
    @param upTo the last number to check
    @return a list of all prime numbers less than or equal to upTo
    """
    primeList = [2]
    primeSearch = []
    for n in range(3, upTo+1, 2):
        isPrime = True
        for p in primeSearch:
            if p > math.sqrt(n):
                break;
            if n % p == 0:
                isPrime = False
                break;
        if(isPrime):
            primeList.append(n)
            primeSearch.append(n)
    return primeList

def are_coprime(a, b):
    """
    Uses Euclid's algorithm to determine whether or not two numbers are coprime.
    
    @param a a positive integer
    @param b a positive integer
    @return True if (a, b) are coprime; otherwise false
    """
    while b != 0:
        t = b
        b = a % b
        a = t
    return (a == 1)